// 快排

let quick = (arr) => {
  if (!Array.isArray(arr)) return `这不是一个数组`
  if (arr.length < 1) return []
  function quickSort(arr, i, j) {
    if (i < j) {
      let left = i;
      let right = j;
      let mid = Math.floor((left + right) / 2);
      [arr[left], arr[mid]] = [arr[mid], arr[mid]]
      let pivot = arr[left];
      while (i < j) {
        while (arr[j] >= pivot && i < j) {  // 从后往前找比基准小的数
          j--;
        }
        if (i < j) {
          arr[i++] = arr[j];
        }
        while (arr[i] <= pivot && i < j) {  // 从前往后找比基准大的数
          i++;
        }
        if (i < j) {
          arr[j--] = arr[i];
        }
      }
      arr[i] = pivot;
      quickSort(arr, left, i - 1);
      quickSort(arr, i + 1, right);
      return arr;
    }
  }

  return quickSort(arr, 0, arr.length)
}



let arr = [1, 341, 1, 31, 3, 67, 7, 4, 46, 98, 133]
console.time()
console.log(quick(arr))
console.timeEnd()


console.time()
console.log(arr.sort((a, b) => a - b))
console.timeEnd()